In this paper, we introduce a sparse approximation property of order $s$ fora measurement matrix ${\bf A}$: $$\|{\bf x}_s\|_2\le D \|{\bf A}{\bf x}\|_2+\beta \frac{\sigma_s({\bf x})}{\sqrt{s}} \quad {\rm for\ all} \ {\bf x},$$where ${\bf x}_s$ is the best $s$-sparse approximation of the vector ${\bf x}$in $\ell^2$, $\sigma_s({\bf x})$ is the $s$-sparse approximation error of thevector ${\bf x}$ in $\ell^1$, and $D$ and $\beta$ are positive constants. Thesparse approximation property for a measurement matrix can be thought of as aweaker version of its restricted isometry property and a stronger version ofits null space property. In this paper, we show that the sparse approximationproperty is an appropriate condition on a measurement matrix to consider stablerecovery of any compressible signal from its noisy measurements. In particular,we show that any compressible signalcan be stably recovered from its noisymeasurements via solving an $\ell^1$-minimization problem if the measurementmatrix has the sparse approximation property with $\beta\in (0,1)$, andconversely the measurement matrix has the sparse approximation property with$\beta\in (0,\infty)$ if any compressible signal can be stably recovered fromits noisy measurements via solving an $\ell^1$-minimization problem.
展开▼
